
package cz.cuni.mff.abacs.tools;

import java.math.BigInteger;


/**
 * Systematically generates combinations.
 * 
 * Algorithm by Kenneth H. Rosen, Discrete Mathematics and Its Applications,
 * 2nd edition (NY: McGraw-Hill, 1991), pp. 284-286.
 * 
 * 
 * 
 * @author Michael Gilleland
 *
 */
public class CombinationGenerator {
	
	
	private int[] _a;
	/**
	 * Number of elements to choose from
	 */
	private int _n;
	/**
	 * Length of combinations
	 */
	private int _r;
	private BigInteger _numLeft;
	private BigInteger _total;
	
	
	//--------------------------------------------------------------------------
	// constructors:
	
	
	/**
	 * 
	 * @param n Number of elements to choose from
	 * @param r Length of combinations
	 */
	public CombinationGenerator(int n, int r) {
		if(r > n){
			throw new IllegalArgumentException ();
		}
		if(n < 1){
			throw new IllegalArgumentException ();
		}
		
		this._n = n;
		this._r = r;
		
		this._a = new int[r];
		BigInteger nFact = getFactorial(n);
		BigInteger rFact = getFactorial(r);
		BigInteger nminusrFact = getFactorial(n - r);
		this._total = nFact.divide(rFact.multiply(nminusrFact));
		reset();
	}
	
	
	// -------------------------------------------------------------------------
	
	
	/**
	 * 
	 */
	public void reset() {
		for(int i = 0; i < this._a.length; i++){
			this._a[i] = i;
		}
		this._numLeft = new BigInteger(this._total.toString());
	}
	
	
	/**
	 * Return number of combinations not yet generated
	 * 
	 * @return
	 */
	public BigInteger getNumLeft() {
		return this._numLeft;
	}
	
	
	/**
	 * Are there more combinations?
	 *  
	 * @return
	 */
	public boolean hasMore() {
		return this._numLeft.compareTo(BigInteger.ZERO) == 1;
	}
	
	
	/**
	 * Return total number of combinations
	 * 
	 * @return
	 */
	public BigInteger getTotal() {
		return this._total;
	}
	
	
	/**
	 * Compute factorial
	 * 
	 * @param n
	 * @return
	 */
	private static BigInteger getFactorial(int n) {
		BigInteger fact = BigInteger.ONE;
		for(int i = n; i > 1; i--){
			fact = fact.multiply(new BigInteger(Integer.toString(i)));
		}
		return fact;
	}
	
	
	/**
	 * Generate next combination (algorithm from Rosen p. 286)
	 * 
	 * @return
	 */
	public int[] getNext() {
		if(this._numLeft.equals(this._total)){
			this._numLeft = this._numLeft.subtract(BigInteger.ONE);
			return this._a;
		}
		
		int i = this._r - 1;
		while(this._a[i] == this._n - this._r + i){
			i--;
		}
		this._a[i] = this._a[i] + 1;
		for(int j = i + 1; j < this._r; j++){
			this._a[j] = this._a[i] + j - i;
		}
		
		this._numLeft = this._numLeft.subtract(BigInteger.ONE);
		return this._a;
	}
	
	
}
